//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 
//
// 换句话说，s1 的排列之一是 s2 的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入：s1= "ab" s2 = "eidboaoo"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 10⁴ 
// s1 和 s2 仅包含小写字母 
// 
// Related Topics 哈希表 双指针 字符串 滑动窗口 👍 682 👎 0

package leetcode.editor.cn;

import java.util.*;

class PermutationInString {
    public static void main(String[] args) {
        Solution solution = new PermutationInString().new Solution();
        solution.checkInclusion("ab", "eidbaooo");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 固定大小的滑动窗口
         *
         * @param s1
         * @param s2
         * @return
         */
        /*public boolean checkInclusion(String s1, String s2) {
            // s1的hash表
            int[] record = new int[26];
            // 滑动窗口的哈希表
            int[] window = new int[26];

            // 先将s1放入哈希表
            for (int i = 0; i < s1.length(); i++) {
                record[s1.charAt(i) - 'a'] += 1;
            }

            int left = 0, right = 0;
            for (; right < s2.length(); right++) {
                window[s2.charAt(right) - 'a'] += 1;
                // 固定大小的滑动窗口
                if (right - left + 1 == s1.length()) {
                    if (Arrays.equals(window, record)) {
                        // 返回true即可
                        return true;
                    }
                    window[s2.charAt(left) - 'a'] -= 1;
                    left++;
                }
            }
            return false;
        }*/
        /*public boolean checkInclusion(String s1, String s2) {
            // s2的哈希表
            Map<Character, Integer> map = new HashMap<>();
            // 滑动窗口的哈希表
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0, valid = 0;

            for (int i = 0; i < s1.length(); i++) {
                map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
            }

            while (right < s2.length()) {
                char c = s2.charAt(right);
                if (map.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (map.get(c).equals(window.get(c))) {
                        valid++;
                    }
                }

                right++;

                // 判断是否要收缩，由于求得是排列，所以根据长度来收缩
                while (right - left == s1.length()) {

                    // 如果找到了合法的子串
                    if (valid == map.size()) return true;

                    // 收缩窗口
                    char c1 = s2.charAt(left);
                    if (map.containsKey(c1)) {
                        if (map.get(c1).equals(window.get(c1))) {
                            valid--;
                        }
                        window.put(c1, window.getOrDefault(c1, 0) - 1);
                    }
                    left++;
                }
            }

            return false;
        }*/

        // 固定的滑动窗口
        public boolean checkInclusion(String s1, String s2) {
            // s1的hash表
            int[] record = new int[26];
            // 滑动窗口的哈希表
            int[] window = new int[26];
            int left = 0, right = 0;

            for (int i = 0; i < s1.length(); i++) {
                record[s1.charAt(i) - 'a']++;
            }

            while (right < s2.length()) {
                window[s2.charAt(right) - 'a']++;
                right++;
                while (right - left == s1.length()) {
                    if (Arrays.equals(record, window)) return true;
                    window[s2.charAt(left) - 'a']--;
                    left++;
                }
            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
